// Arrangment and permutation
// 组合（元素无重可复选）
/*
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。
*/
#include <bits/stdc++.h>
using namespace std;

template <typename T>
void printVector(vector<T> nums, bool withEnter=true)
{
    for (auto n : nums)
    {
        cout << n << ' ';
    }
    if(withEnter)
        cout<<endl;
}

// [组合]
// 题目给你输入一个无重复元素的数组 nums,
// 从 nums 中找出中所有和为 target 的组合。
vector<vector<int>> res;
vector<int> path;
int pathSum = 0;

void backtrack(vector<int> &nums,int startIndex,int target){
    if(pathSum == target){
        res.push_back(path);
        return;
    }
    if(pathSum > target){
        return; // 在 nums均为正数时可以直接跳过
    }

    for(int i = startIndex; i < nums.size(); i++){
        path.push_back(nums[i]);
        pathSum += nums[i];
        backtrack(nums,i,target);
        pathSum -= nums[i];
        path.pop_back();
    }
    return;
}

vector<vector<int>> combine(vector<int> nums, int target){
    sort(nums.begin(),nums.end());
    backtrack(nums,0, target);
    return res;
}

int main(){
    vector<int> nums = {10,1,2,7,6,5};
    int target = 8;

    vector<vector<int>> res = combine(nums,target);
    for(auto line : res){
        printVector(line);
    }
    return 0;
}